#! /usr/bin/env python
# -*-coding:utf-8 -*-

class Node(object):
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node
        self.prev = None # contains the reference to the previous node

class LinkedListIter(object):
    def __init__(self, linked_list):
        self._current_node = linked_list.getStartNode()
        
    def __iter__(self):
        return self

    def __next__(self):
        if self._current_node is not None:
            current_node = self._current_node
            self._current_node = self._current_node.next
            return current_node.data
        else:
            raise StopIteration()
        
class LinkedList(object):
    def __init__(self):
        self._start_node = None
        self._end_node = None
        self._node_num = 0
        self._current_node = None
        
    def getStartNode(self):
        return self._start_node

    def add(self, data):
        self.insert(-1, data)
        
    def insert(self, i, data):
        """
        在索引为i的节点后插入新的节点，新节点中的数据为data。
        """
        #print('inserting node at', i)
        if i > self._node_num or i < -self._node_num-1:
            return None
        new_node = Node()
        new_node.data = data
        if i < 0:
            i += self._node_num + 1
        if i == self._node_num:
            if self._end_node is not None:
                self._end_node.next = new_node
            new_node.prev = self._end_node
            self._end_node = new_node
        else:
            u = self.getNode(i)
            v = u.prev
            u.prev = new_node
            new_node.prev = v
            new_node.next = u
            if v is not None:
                v.next = new_node
        if i == 0:
                               
            self._start_node = new_node
        self._node_num += 1
        return new_node
              
    def remove(self, i):
        #print('removing node at', i)
        if self._node_num == 0:
            raise ValueError('The linked-list is empty.')
        elif  i >= self._node_num or i < -self._node_num:
            raise ValueError('The index is out or range.')
            
        u = self.getNode(i)
        if u.prev is not None:
            u.prev.next = u.next
            #print('u.prev.next updated to', u.prev.next)
        if u.next is not None:
            u.next.prev = u.prev
        if i == 0:
            self._start_node = u.next
        if i == self._node_num - 1:
            self._end_node = u.prev
        del u
        
        self._node_num -= 1
        
    def move(self, fr, to):
        #print('moving node from', fr, 'to', to)
        if fr == to:
            return
            
        if fr >= self._node_num or fr < -self._node_num or \
           to >= self._node_num or to < -self._node_num:
            return
            
        if fr < 0:
            fr += self._node_num
        if to < 0:
            to += self._node_num
            
        f = self.getNode(fr)
        t = self.getNode(to)
        
        if fr == 0:
            self._start_node = self._start_node.next
        elif fr == self._node_num - 1:
            self._end_node = self._end_node.prev
        if to == 0:
            self._start_node = f    
        elif to == self._node_num - 1:
            self._end_node = f
            
        #print('start node', self._start_node)
        #print('end node', self._end_node)
        
        if f.prev is not None:
            f.prev.next = f.next
        if f.next is not None:
            f.next.prev = f.prev
        if fr > to:
            if t.prev is not None:
                t.prev.next = f
            f.prev = t.prev
            f.next = t
            t.prev = f
        if fr < to:
            if t.next is not None:
                t.next.prev = f
            f.prev = t
            f.next = t.next
            t.next = f
            
    def swap(self, i, j):
        if i == j:
            return
        a, b = min(i, j), max(i, j)
        self.move(b, a)
        self.move(a+1, b)
            
    def getNode(self, i):
        if self._node_num == 0 or i >= self._node_num or i < -self._node_num:
            return None
            
        if i < 0:
            i = self._node_num + i
        node = self._start_node
        while i > 0:
            node = node.next
            i -= 1
        return node
        
    def get(self, i):
        node = self.getNode(i)
        if node is None:
            return None
        else:
            return node.data
            
    def size(self):
        return self._node_num
        
    def empty(self):
        return self._node_num == 0
 
    def __getitem__(self, idx):
        """
        获取复合任务队列的下标为idx的复合任务。
        :return: 复合任务队列的一个迭代器。
        """
        return self.get(idx)
        
def testLinkedList():
    ll = LinkedList()
    ll.add(1)
    ll.add(2)
    ll.add(3)
    ll.add(5)
    ll.swap(0, 3)    
    n = ll.getStartNode()
    print(n.data)
    print(n.next.data)